#define _CRT_SECURE_NO_WARNINGS 1
#include"test.h"

typedef struct ListNode ListNode;
ListNode* SLBuyNode(int x) {
    ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
    if (newnode == NULL)
        exit(1);
    newnode->val = x;
    newnode->next = NULL;
    return newnode;
}

ListNode* createNode(int n) {
    ListNode* phead = SLBuyNode(1);
    ListNode* ptail = phead;
    for (int i = 2; i <= n; i++) {
        ptail->next = SLBuyNode(i);
        ptail = ptail->next;
    }
    ptail->next = phead;
    return ptail;
}

int ysf(int n, int m) {
    ListNode* prev = createNode(n);
    ListNode* pcur = prev->next;
    int count = 1;
    while (pcur->next != pcur) {
        if (count == m) {
            prev->next = pcur->next;
            free(pcur);
            pcur = prev->next;
            count = 1;
        }
        else {
            prev = pcur;
            pcur = pcur->next;
            count++;
        }
    }
    return pcur->val;
}

    ListNode* partition(struct ListNode* head, int x) {
    if (head == NULL)
        return head;
    ListNode* lesshead, * lesstail;
    ListNode* greaterhead, * greatertail;
    lesshead = lesstail = (ListNode*)malloc(sizeof(ListNode));
    greaterhead = greatertail = (ListNode*)malloc(sizeof(ListNode));
    ListNode* pcur = head;
    while (pcur) {
        if (pcur->val < x) {
            lesstail->next = pcur;
            lesstail = lesstail->next;
        }
        else {
            greatertail->next = pcur;
            greatertail = greatertail->next;
        }
        pcur = pcur->next;
    }
    greatertail->next = NULL;
    lesstail->next = greaterhead->next;


    ListNode* ret = lesshead->next;
    free(lesshead);
    free(greaterhead);
    return ret;
}